import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution438 {
    public List<Integer> findAnagrams(String s, String p) {
        // 用于存储结果的列表
        List<Integer> result = new ArrayList<>();

        // need 表记录目标字符串 p 中所需字符的频率
        Map<Character, Integer> need = new HashMap<>();
        // window 表记录当前滑动窗口中相关字符的频率
        Map<Character, Integer> window = new HashMap<>();

        for (char c : p.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        // valid 变量表示窗口中满足 need 条件的字符种类数
        int valid = 0;

        // 主循环，移动 right 指针扩大窗口
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;

            // 如果新移入的字符是目标字符，则更新 window 和 valid
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }

            // 【收缩窗口的条件】：窗口长度达到了 p 的长度
            while (right - left >= p.length()) {
                // 【更新答案的条件】：当窗口长度固定，且窗口内字符满足要求时
                if (valid == need.size()) {
                    result.add(left);
                }

                // 准备将 s[left] 移出窗口
                char d = s.charAt(left);
                left++;

                // 如果移出的字符是目标字符，则更新 window 和 valid
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    // 【关键遗漏点】更新 window 中的计数
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        // 循环结束后返回结果
        return result;
    }
}